package alogrithm.solution;

import alogrithm.structure.LinkedNode;

/*
 * 微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?(还没实现)
2.如果需要求出俩个链表相交的第一个节点列?（已经实现）
 */
public class P7 {
	public static LinkedNode findFirstCommonNode(LinkedNode n1,LinkedNode n2)
	{
		LinkedNode p1=n1,p2=n2;
		if(p1==null||p2==null)return null;
		int l1=1,l2=1;
		while(p1.getPost()!=null)
		{
			p1=p1.getPost();
			l1++;
		}
		while(p2.getPost()!=null)
		{
			p2=p2.getPost();
			l2++;
		}
		if(p1!=p2)return null;
		if(l2-l1>0)
		{
			LinkedNode tmp=n1;
			n1=n2;
			n2=tmp;;
			int l=l1;
			l1=l2;
			l2=l;
		}
		int gap=l1-l2;
		p1=n1;p2=n2;
		while(gap--!=0)p1=p1.getPost();
		while(p1!=p2)
		{
			p1=p1.getPost();
			p2=p2.getPost();
		}
		return p1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LinkedNode n4=new LinkedNode(5,null);
		LinkedNode n3=new LinkedNode(3,n4);
		LinkedNode n2=new LinkedNode(2,n3);
		LinkedNode n5=new LinkedNode(4,n3);
		LinkedNode n1=new LinkedNode(1,n2);
		LinkedNode commonNode=findFirstCommonNode(n5, n1);
		if(commonNode!=null)
			System.out.println(commonNode.getValue());
		

	}

}
